package com.example.sortingalgorithm;

// 【选择排序】算法
public class SelectionSort {

    /**
     * 【选择排序】算法
     * 选择排序的思路是：
     * 对于长度为n的待排序序列，首先通过n-1次比较找出最小值，然后将最小值的元素和待排序序列的最前端的元素进行交换位置，这就完成了第1趟排序。
     * 由于最小的元素已经排在了最前端，那么待排序序列的长度就变成了n-1，接下来只需要通过同样的方法确定出这个长度为n-1的待排序序列中的最小值元素，然后交换。
     * 总共要比较n-1趟排序。
     * 例如：
     * [4] [5] [3] [1] [2]
     * a0  a1  a2  a3  a4
     * 第1趟排序后变成：
     * [1] [5] [3] [4] [2]
     * a0  a1  a2  a3  a4
     * 第2趟排序后变成：
     * [1] [2] [3] [4] [5]
     * a0  a1  a2  a3  a4
     * @param array 待排序数组
     * @param <T>
     */
    public static <T extends Comparable> void sort(T[] array){

        // 记录每一轮比较中最小值的位置
        int minimumValueIndex;
        T temp = null;

        // i 代表第几趟排序
        for(int i = 1; i <= array.length-1; i++){

            // minimumValueIndex的初始值设置为待排序序列的第一个个元素的下标
            minimumValueIndex = i - 1;
            for(int j = i; j <= array.length-1; j++){
                // 如果array[j]的值比array[minimumValueIndex]的值要小，那么将minimumValueIndex的值变成j
                if(array[j].compareTo(array[minimumValueIndex]) < 0){
                    minimumValueIndex = j;
                }
            }
            // 将最小值元素和待排序序列的首元素进行值交换
            temp = array[i-1];
            array[i-1] = array[minimumValueIndex];
            array[minimumValueIndex] = temp;
        }
    }
}
